1. Field of the Invention
The present invention relates to the field of microprocessor architecture. More specifically, the present invention relates to the field of microprocessor architecture for coordinating instructions executed in parallel which require common resources by providing a method and apparatus for extending execution unit pipelines.
2. Art Background
As the computer revolution has progressed the quest of microprocessor developers has been to develop chips exhibiting more power and faster performance. Initial efforts focused essentially on increasing transistor populations on single microprocessor integrated circuits. That effort continues with today's microprocessors now housing literally millions of transistors on a single chip. Further integration has allowed processor clock speeds to be greatly increased with the increased density of transistors.
In addition to squeezing performance by overcoming physical limitations, microprocessor design has developed into an art form. Microprocessors are divided into discrete functional blocks through which instructions are propagated one stage at a time. This allows for pipelining of instructions such that when one instruction has completed the first stage of processing and moves on to the second stage, a second instruction may begin the first stage. Thus, even where each instruction requires a number of clock cycles to complete all stages of processing, pipelining provides for the completion of instructions on every clock cycle. This single-cycle throughput of a pipelined microprocessor greatly increases the overall performance of computer systems.
Other enhancements to microprocessor design include the development of superscalar microprocessors which are capable of launching more than one instruction at the initial stage of the pipeline per clock cycle. Likewise, in a superscalar microprocessor, frequently more than one instruction completes on each given clock cycle. Other development efforts have gone into the simplification of microprocessor instruction sets, developing reduced instruction set (RISC) microprocessors which exploit the fact that many simple instructions are more commonly executed than some complicated instructions. Eliminating the complicated instructions from the instruction set provides for a faster executing pipeline. Complicated instructions are carried out by combinations of the more simple instructions.
In order for pipelined microprocessors to operate efficiently, an instruction fetch unit at the head of the pipeline must continually provide the pipeline with a stream of instructions. However, conditional branch instructions within an instruction stream prevent an instruction fetch unit at the head of a pipeline from fetching the correct instruction until the condition is resolved. Since the condition will not be resolved until further down the pipeline, the instruction fetch unit may not be able to fetch proper instructions.
To overcome this problem, many pipelined microprocessors use branch prediction mechanisms that predict the outcome of branches and then fetch subsequent instructions according to branch prediction. Branch prediction is achieved using a branch target buffer to store the history of a branch instruction based upon the instruction pointer or address of that instruction. Every time a branch instruction is fetched, the branch target buffer predicts the target address of the branch using the branch history. The use of branch prediction in a pipelined instruction architecture is often referred to as speculative execution.
In addition to speculative execution, substantial increases in instruction throughput are achievable by implementing out-of-order dispatch of instructions to the execution units. Many experiments have confirmed that typical von Neumann code provides substantial parallelism and hence a potential performance boost by use of out-of-order execution. Out-of-order execution is possible when a given instruction does not depend on previous instructions for a result before executing. With out-of-order execution, any number of instructions are allowed to be in execution in the execution units, up to the total number of pipeline stages for all the functional units.
In a processor using out-of-order execution, instruction issuing is stalled when there is a conflict for a functional unit or when an issued instruction depends on the result of an instruction that is not yet computed. In order to prevent or mitigate stalls in decoding, previous texts have described the provision of a buffer known as a reservation station (RS) between the decode and execute stages. The processor decodes instructions and places them into the reservation station as long as there is room in the buffer and at the same time examines instructions in the reservation station to find those that can be dispatched to the execution units (that is, instructions for which source operands and execution units are available). Data-ready instructions are issued from the reservation station with little regard for their original program order. For a further description of the use of a reservation station and out-of-order execution, see Mike Johnson, Superscalar Microprocessor Design and Prentice-Hall, Inc., 1991, Chapters 3 and 7.
In microprocessors implementing reservation stations, including superscalar processors, the reservation station will generally provide ready instructions directly from the reservation station to an appropriate execution unit. In many cases execution units may be grouped together coupled from a single dispatch port from the reservation station. For example, one implementation may have floating point add and floating point multiply execution units coupled through the same dispatch port. Floating point add and floating point multiply execution units may have differing length internal pipelines. A problem arises because these commonly grouped execution units may share a single writeback path from the execution units. If the reservation station dispatches a first instruction to an execution unit such as to the floating point multiply unit and then subsequently dispatches an instruction to the floating point add execution unit in a common group of execution units, it is possible that multiple execution units will be ready to write back a result at the same time. Because the execution units share a common writeback port, a contention develops.
It is an object of the present invention to overcome the contention of execution units which share a common writeback port and which face this contention possibility.